package com.topcoder.srm517;

import java.util.Arrays;
import java.util.Comparator;

public class CuttingGrass {
	private Grass[]	g;
	
	public int theMin(int[] init, int[] grow, int H) {
		int N = init.length;
		g = new Grass[N];
		for (int i=0; i<N; i++) {
			g[i] = new Grass(init[i], grow[i]);
		}
		Arrays.sort(g, new Comparator<Grass>() {
			public int compare(Grass a, Grass b) {
				if (a.grow == b.grow) return b.init - a.init;
				return a.grow - b.grow;
			}
		});
		
		for (int D=0; D<=N; D++) {
			int[][] min = new int[N+1][D+1];
			for (int i=N-1; i>=0; i--) {
				min[i][D] = min[i+1][D] + g[i].init + D*g[i].grow;
			}
			
			for (int day=D-1; day>=0; day--) {
				for (int pos=N-1; pos>=0; pos--) {
					int noCut = g[pos].init + D*g[pos].grow + min[pos+1][day];
					int cut = (D - day - 1)*g[pos].grow + min[pos+1][day+1];
					min[pos][day] = Math.min(noCut, cut);
				}
			}
			if (min[0][0] <= H) return D;
		}
		
		return -1;
	}
	
	private class Grass {
		int init, grow;
		public Grass(int init, int grow) {
			this.init = init;
			this.grow = grow;
		}
	}
}
